In the past several decades, the proliferation of a common set of distributed routing protocols has empowered growth of interconnectivity and facilitated the development of large inter-domain networks like the Internet. In inter-domain networks, the control system generally consists of a set of routers under the administrative control of different organizations that collectively exchange and act upon the connectivity information received from the routers of neighboring organizations. These organizations generally are Internet Service Providers (“ISPs”), non-ISP corporations, or other organizations that, through their connections, form the Internet.
In general, this interconnectivity has relied on topology-agnostic route exchange mechanisms in which neighboring networks exchange information with one another about what networks can be reached. For example, in conventional approaches, routing messages are often exchanged exclusively between neighboring networks by configuring respective routers in a peering relationship using Border Gateway Protocol (“BGP”). Under current protocol-defined behaviors, when a first router of one network receives a BGP message from a second router of another network, the first router analyzes the information contained in the message. If the message helps the first router to form an ideal path to the message destination, the first router redistributes the message to its neighboring routers. Using this methodology for routing, messages containing network-related routing information propagate throughout a much larger network (such as the Internet) on a “hop-by-hop” basis in a conceptually similar manner to individuals passing information through “hear-say” communication. When all participants follow this approach, enough information may be distributed to allow for interconnectivity between thousands of networks, even though a single network may only be directly connected to a few networks.
The ultimate goal of exchanging this connectivity information is to create a distributed process that facilitates multi-hop forwarding paths from any source to any destination user of the large set of connected networks—ideally along an optimal path. In the general case, the ability to make an optimal next hop decision for a particular fragment of information requires that each network participant be informed of the underlying neighbor connectivity and any identified path restrictions. As networks grow due to the addition of participant organizations and experience increasingly dynamic behavior caused by nodes joining or leaving the network, the task of efficiently distributing the necessary control information to make these decisions also increases in complexity.
The elementary case in inter-domain routing is that each participant has at least one unique piece of information that is of interest to every other participant of the distributed system, and therefore requires sending this message to the rest of the n−1 participants. If n participants transmit each of their unique messages to n−1 participants, the collective task of distributing routing information for the entire system can be generalized as having a distribution complexity of O(n2) (commonly known as “Big Oh” notation in computer science). In systems like the Internet that include millions of routers, the task of distributing this routing information to nodes within the existing bandwidth limitations can take a considerable amount of time, exacerbated by the effects of dropped packets, duplicate message transmissions, and congested communication links. For networking systems in particular, delays caused by routing updates may be frustrating to users because the physical connectivity is available, but data cannot traverse the network because participant networks have not received the needed information to facilitate the flow of traffic.
While this single router-to-router information dissemination approach has helped to facilitate the incremental growth and expansion of the Internet, such conventional approaches struggle to provide adequate convergence performance to accommodate for future network growth, to accommodate the control plane dynamics caused by mobile networks, and to counter network security threats. For example, the distribution of routing updates through BGP may take minutes, or in some cases hours, to propagate across the entire Internet. During the time these routing updates are propagating, a user cannot assume that traffic will be properly delivered to the intended destination, thus lowering the utility of the network. Beyond these delays, many of the messages transmitted in existing BGP implementations are wasteful in the sense that they contain duplicate or incorrect information.
Also, mobile networks have not been widely integrated with the inter-domain routing processes of the Internet. Instead, methodologies for providing routing-like services for mobile nodes have predominantly consisted of tunneling and agent-based forwarding that create path forwarding inefficiencies. Further, current routing protocols of the Internet are considered vulnerable because no globally accepted mechanism exists for preventing malicious nodes from falsifying information in a routing message to divert traffic in a harmful way from other targeted routing participants. Accordingly, routing protocols, infrastructure, and devices that address these issues may be beneficial.